Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7]
Example 2:
Input: inorder = [-1], postorder = [-1] Output: [-1]
Constraints:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorderandpostorderconsist of unique values.- Each value of
postorderalso appears ininorder. inorderis guaranteed to be the inorder traversal of the tree.postorderis guaranteed to be the postorder traversal of the tree.
Average Rating: 4.71 (63 votes)
Solution
How to traverse the tree
There are two general strategies to traverse a tree:
-
Depth First Search (
DFS)In this strategy, we adopt the
depthas the priority, so that one would start from a root and reach all the way down to certain leaf, and then back to root to reach another branch.The DFS strategy can further be distinguished as
preorder,inorder, andpostorderdepending on the relative order among the root node, left node and right node. -
Breadth First Search (
BFS)We scan through the tree level by level, following the order of height, from top to bottom. The nodes on higher level would be visited before the ones with lower levels.
On the following figure the nodes are enumerated in the order you visit them,
please follow 1-2-3-4-5 to compare different strategies.
In this problem one deals with inorder and postorder traversals.
Approach 1: Recursion
How to construct the tree from two traversals: inorder and preorder/postorder/etc
Problems like this one are often at Facebook interviews, and could be solved in O(N) time:
-
Start from not inorder traversal, usually it's preorder or postorder one, and use the traversal picture above to define the strategy to pick the nodes. For example, for preorder traversal the first value is a root, then its left child, then its right child, etc. For postorder traversal the last value is a root, then its right child, then its left child, etc.
-
The value picked from preorder/postorder traversal splits the inorder traversal into left and right subtrees. The only information one needs from inorder - if the current subtree is empty (= return
None) or not (= continue to construct the subtree).
Algorithm
-
Build hashmap
value -> its indexfor inorder traversal. -
Return
helperfunction which takes as the arguments the left and right boundaries for the current subtree in the inorder traversal. These boundaries are used only to check if the subtree is empty or not. Here is how it workshelper(in_left = 0, in_right = n - 1):-
If
in_left > in_right, the subtree is empty, returnNone. -
Pick the last element in postorder traversal as a root.
-
Root value has index
indexin the inorder traversal, elements fromin_lefttoindex - 1belong to the left subtree, and elements fromindex + 1toin_rightbelong to the right subtree. -
Following the postorder logic, proceed recursively first to construct the right subtree
helper(index + 1, in_right)and then to construct the left subtreehelper(in_left, index - 1). -
Return
root.
-
Implementation
Complexity Analysis
-
Time complexity : O(N). Let's compute the solution with the help of master theorem T(N)=aT(Nb)+Θ(Nd). The equation represents dividing the problem up into a subproblems of size bN in Θ(Nd) time. Here one divides the problem in two subproblemes
a = 2, the size of each subproblem (to compute left and right subtree) is a half of initial problemb = 2, and all this happens in a constant timed = 0. That means that logb(a)>d and hence we're dealing with case 1 that means O(Nlogb(a))=O(N) time complexity. -
Space complexity : O(N), since we store the entire tree.
September 2, 2019 2:22 AM
What is the reason that we have to construct the right sub-tree first and then the left sub-tree?
November 12, 2020 5:51 PM
[Java] Recursive | Easy to understand
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length == 0 || postorder.length == 0) return null;
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
if(postorder.length == 1) return root;
int index = 0;
for(int val : inorder){
if(val == root.val) break;
index++;
}
root.left = buildTree(Arrays.copyOfRange(inorder, 0, index), Arrays.copyOfRange(postorder, 0, index));
root.right = buildTree(Arrays.copyOfRange(inorder, index + 1, inorder.length), Arrays.copyOfRange(postorder, index, postorder.length - 1));
return root;
}
Last Edit: February 2, 2020 6:16 PM
Refer to the greate answer of @StefanPochmann in this post.
It's possible to reach O(N) time without the index map.
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
def build(bound = None):
if not inorder or inorder[-1] == bound: return None
root = TreeNode(postorder.pop())
root.right = build(root.val)
inorder.pop()
root.left = build(bound)
return root
return build()
January 24, 2020 1:10 AM
Since we are popping nodes from the end from post-order list, we come across nodes in the order: node, node.right and then node.left
A very simple Python implementation.
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not inorder:
return None
cur_val = postorder.pop()
idx = inorder.index(cur_val)
right = self.buildTree(inorder[idx+1:], postorder)
left = self.buildTree(inorder[:idx], postorder)
return TreeNode(cur_val, left, right)
My js solution
var splitArray = (arr, splitter) => {
const index = arr.indexOf(splitter);
const left = arr.slice(0, index);
const right = arr.slice(index + 1);
return { left, right };
}
var buildTree = function(inorder, postorder) {
if (!inorder.length) {
return null;
}
const current = postorder.pop();
const isLeaf = inorder.length === 1;
if (isLeaf) {
return {
val: current,
left: null,
right: null,
}
}
const splitted = splitArray(inorder, current);
return {
val: current,
right: buildTree(splitted.right, postorder),
left: buildTree(splitted.left, postorder),
}
};
August 25, 2020 9:18 AM
var buildTree = function(inorder, postorder) {
if (inorder.length === 0) return null;
if (inorder.length === 1) return new TreeNode(inorder[0]);
const rootVal = postorder.pop();
const leftInOrder = inorder.slice(0, inorder.indexOf(rootVal));
const rightInOrder = inorder.slice(inorder.indexOf(rootVal)+1, inorder.length);
const leftPostOrder = postorder.slice(0, leftInOrder.length);
const rightPostOrder = postorder.slice(leftInOrder.length, postorder.length);
const leftTreeNode = buildTree(leftInOrder, leftPostOrder);
const rightTreeNode = buildTree(rightInOrder, rightPostOrder);
return new TreeNode(rootVal, leftTreeNode, rightTreeNode);
};
Why is the size of each subproblem half the size of the initial problem? If you have a very unbalanced graph you can have two subproblems one of size 999999 (N-1) and the other with size 1, in that case isn't b very close to 1 and not 2?
JS recursive solution:
var buildTree = function(inorder, postorder) {
if (!postorder.length) return null;
if (postorder.length === 1) {
return new TreeNode(postorder[0])
} else {
const val = postorder.pop();
const idx = inorder.indexOf(val);
return new TreeNode(
val,
buildTree(inorder.slice(0, idx), postorder.slice(0, idx)),
buildTree(inorder.slice(idx + 1), postorder.slice(idx)),
)
}
};
I've managed to solve the problem with iteration and a stack. I've been trying really hard to prove why this solution works, but I'm having trouble solidly articulating it. If anyone knows how to put into words why this solution works I'd really appreciate the help.
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not postorder:
return None
postIter = reversed(postorder)
root = TreeNode(next(postIter))
parentStack = [root]
i = len(inorder) - 1
for val in postIter:
node = TreeNode(val)
if inorder[i] == parentStack[-1].val:
i -= 1
parent = parentStack.pop()
while parentStack and inorder[i] == parentStack[-1].val:
parent = parentStack.pop()
i -= 1
parent.left = node
parentStack.append(node)
else:
parentStack[-1].right = node
parentStack.append(node)
return root
x
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution { public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { this->inorder = inorder; this->postorder = postorder; postIndex = postorder.size() - 1; // build hashmap (value -> inorder index) int idx = 0; for(int val : inorder) { mp[val] = idx; idx++; } return helper(0, inorder.size()-1); } private: int postIndex; vector<int> postorder; vector<int> inorder; unordered_map<int,int> mp; // value -> inorder idx TreeNode* helper(int inLeft, int inRight) { // No element to construct subtrees if(inLeft > inRight) return NULL; // post index element will be the root int rootVal = postorder[postIndex]; TreeNode* root = new TreeNode(rootVal); // the root splits inorder list into left and right subtree int index = mp[rootVal]; postIndex--; // build the right and left tree recursively root->right = helper(index+1, inRight); root->left = helper(inLeft, index-1); return root; }};

